package net.jcip.examples;

import java.util.*;
import java.util.concurrent.*;

/**
 * ConcurrentPuzzleSolver
 * <p/>
 * Concurrent version of puzzle solver
 * @author Brian Goetz and Tim Peierls
 */
public class ConcurrentPuzzleSolver<P, M> {
	private final Puzzle<P, M> puzzle;
	private final ExecutorService exec;
	private final ConcurrentMap<P, Boolean> seen;
	protected final ValueLatch<PuzzleNode<P, M>> solution = new ValueLatch<PuzzleNode<P, M>>();

	public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle) {
		this.puzzle = puzzle;
		this.exec = initThreadPool();
		this.seen = new ConcurrentHashMap<P, Boolean>();
		if (exec instanceof ThreadPoolExecutor) {
			ThreadPoolExecutor tpe = (ThreadPoolExecutor) exec;
			tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.DiscardPolicy());
		}
	}

	private ExecutorService initThreadPool() {
		return Executors.newCachedThreadPool();
	}

	public List<M> solve() throws InterruptedException {
		try {
			P p = puzzle.initialPosition();
			exec.execute(newTask(p, null, null));
			// block until solution found
			PuzzleNode<P, M> solnPuzzleNode = solution.getValue();
			return (solnPuzzleNode == null) ? null : solnPuzzleNode.asMoveList();
		} finally {
			exec.shutdown();
		}
	}

	protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) {
		return new SolverTask(p, m, n);
	}

	protected class SolverTask extends PuzzleNode<P, M> implements Runnable {
		SolverTask(P pos, M move, PuzzleNode<P, M> prev) {
			super(pos, move, prev);
		}

		public void run() {
			if (solution.isSet() || seen.putIfAbsent(pos, true) != null)
				return; // already solved or seen this position
			if (puzzle.isGoal(pos))
				solution.setValue(this);
			else
				for (M m : puzzle.legalMoves(pos))
					exec.execute(newTask(puzzle.move(pos, m), m, this));
		}
	}
}
